package impl;

import anaydis.sort.SorterType;
import org.jetbrains.annotations.NotNull;

import java.util.Comparator;
import java.util.List;

public class MergeSorterBottomUp extends AbstractSorter{

    public MergeSorterBottomUp(){
        super(SorterType.MERGE_BOTTOM_UP);
    }

    public <T> void sort(Comparator<T> tComparator, List<T> ts) {
        int i = 2;
        boolean resto = false;
        while(i<ts.size()){
            for(int g = 0; g<(ts.size()/i)+1; g++){
                if((g == ts.size()/i)){
                    if((ts.size()%i!=0 && (ts.size()/i)%2 != 0) || resto){
                        if(resto){
                            merge(tComparator, ts, g*i, ts.size(),(g*i)+i/2);
                            resto = false;
                        }
                        else{
                            resto = true;
                        }
                    }
                }
                else{
                    merge(tComparator, ts, g*i, (g*i)+i,(g*i)+i/2);
                }
            }
            i*=2;
        }
        merge(tComparator, ts, 0, ts.size(), i/2);
    }

    private <T> void merge(Comparator<T> tComparator, List<T> ts, int desde, int hasta, int quiebre){

        int g = desde;
        int h = quiebre;
        int i = 0;
        Object[] aux = new Object[hasta - g];

        //este while compara y agrega al arreglo auxiliar los datos ordenados
        while((g<quiebre) && (h<hasta)){
            if(greater(tComparator, ts, g, h)){
                aux[i] = ts.get(h);
                copy(h, i, true);
                h++;
            }
            else{
                aux[i] = ts.get(g);
                copy(g, i, true);
                g++;
            }
            i++;
        }

        //estos dos while agregan los datos que sobran al aux
        while(g<quiebre){
            aux[i] = ts.get(g);
            copy(g, i, true);
            g++;
            i++;
        }

        while(h<hasta){
            aux[i] = ts.get(h);
            copy(h, i, true);
            h++;
            i++;
        }

        for(int j = 0; j<aux.length;j++){
            ts.set(j+desde, (T)aux[j]);
            copy(j, j+desde, false);
        }
//chequeador de funcionamiento paso a paso
/*
        for(int o = 0; o<ts.size(); o++){
            System.out.print(ts.get(o)+" ");

        }
        System.out.println();
*/
    }

    @NotNull
    public SorterType getType() {
        return SorterType.MERGE_BOTTOM_UP;
    }
}
